package jago02.jago0201.ag02_lineTable;

import java.util.Iterator;

/**
 * 链式表：双向链表
 * 杂化简：双向链表从首节点head开始一直往后追加节点元素，节点存储元素和前节点、下一个节点,尾节点last存储最后一个元素
 *
 * 解目录：
 *      1.用N表示双向链表长度，表示双向链表的元素个数
 *      2.内部类Node包含元素值、前节点、下个节点
 *      4.自然添加元素到双向链表就是新增数据节点，并追加到老尾节点后，老尾节点变成新节点的pre节点，新节点编程老尾节点的next节点，新节点变成尾节点
 *      5.双向链表指定位置添加元素就是循环指定位置index-1次拿到pre节点，然后新增新节点，新增节点pre指向老节点的pre，原pre的next指向新节点，原节点的pre指向新节点，后N++
 *      6.移除双向链表指定位置元素就是循环指定位置index-1次拿到pre节点，然后将pre的next指向index节点的next节点，然后N--，并返回被删除元素
 *      7.查找元素在双向链表位置索引，未找到则返回-1
 * 复杂度：所有方法都是O(N)
 */
public class LineTable03_TwoWayLinkList<T> implements Iterable<T> {
    //节点内部类
    private class Node{
        T item;
        Node pre;
        Node next;
        public Node(T item, Node pre,Node next) {
            this.item = item;
            this.pre = pre;
            this.next = next;
        }
    }

    //头节点
    private Node head;
    //尾节点
    private Node last;
    //双向链表长度
    private int N;
    //构造
    public LineTable03_TwoWayLinkList() {
        this.head = new Node(null,null,null);
        this.last = null;
        this.N = 0;
    }
    //置空双向链表
    public void clear(){
        this.N = 0;
    }
    //双向链表判空
    public boolean isEmpty(){
        return this.N == 0;
    }
    //获取双向链表长度
    public int length(){
        return this.N;
    }

    //获取双向链表第一个元素
    public T getFirst(){
        if (isEmpty()){
            return null;
        }
        return this.head.next.item;
    }

    //获取双向链表最后一个元素
    public T getLast(){
        return this.last.item;
    }

    //向双向链表中插入元素
    public void insert(T t){
        if (isEmpty()){
            //双向链表为空
            //创建新节点
            Node newNode = new Node(t,this.head,null);
            this.last = newNode;
            //让头节点下个节点指向尾节点
            this.head.next = this.last;
        }else {
            //双向链表非空
            //记录之前的尾部节点
            Node oldNode = this.last;
            //创建新结点
            Node newNode = new Node(t,oldNode,null);
            //尾节点指向新节点
            this.last.next = newNode;
            //让新节点成为尾节点
            this.last = newNode;
        }
        this.N++;
    }
    //向双向链表中指定位置插入元素
    public void insert(int index,T t){
        //找到index位置的前一个节点
        Node pre = this.head;
        //找到index位置的节点
        for (int i = 0; i < index-1; i++) {
            pre = pre.next;
        }
        //获取index位置的节点
        Node current = pre.next;
        //创建新节点,新节点的下个节点是current,并将新节点放到pre的next位置
        Node newNode = new Node(t,pre,current);
        pre.next = newNode;
        current.pre  = newNode;
        this.N++;
    }

    public T get(int i){
        //通过循环，从头节点开始往后找，依次找到i，就可以找到对应的元素
        Node node = this.head.next;
        for (int j = 0; j < i; j++) {
            if (node != null){
                node = node.next;
            }else{
                break;
            }
        }
        if (node == null){
            return null;
        }else {
            return node.item;
        }

    }

    //删除并返回双向链表指定索引元素
    public T remove(int index){
        //找到index位置的前一个节点
        Node pre = this.head;
        //找到index位置的节点
        for (int i = 0; i < index-1; i++) {
            pre = pre.next;
        }
        //获取index位置的节点
        Node current = pre.next;
        //找到i位置的下一个节点
        Node nextNode = current.next;
        //前一个节点的next指向下一个节点
        pre.next = nextNode;
        nextNode.pre = pre;
        this.N--;
        return current.item;
    }

    //查找首次出现元素t的位置,找不到则返回-1
    public int indexOf(T t){
        Node node = this.head;
        for (int i = 0; node.next!=null; i++) {
            node = node.next;
            if (node.item.equals(t)){
                return i;
            }
        }
        return -1;
    }


    private class TwoWayLinkListIterator implements Iterator{
        private Node curr;

        public TwoWayLinkListIterator() {
            this.curr = head;
        }

        @Override
        public boolean hasNext() {
            return this.curr.next != null;
        }
        @Override
        public Object next() {
            curr = curr.next;
            return curr.item;
        }
    }

    @Override
    public Iterator iterator() {
        return new TwoWayLinkListIterator();
    }

    public static void main(String[] args) {
        LineTable03_TwoWayLinkList<String> twoWayLinkList = new LineTable03_TwoWayLinkList();
        twoWayLinkList.insert("张三");
        twoWayLinkList.insert("李四");
        twoWayLinkList.insert("王五");
        twoWayLinkList.insert(1,"老朱");
        System.out.println(twoWayLinkList);
        for (String str : twoWayLinkList) {
            System.out.print(str+" ");
        }
    }
}
